package com.zecan.greedAlgorithm;

import java.util.Arrays;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: lenovo
 * \* Date: 2021/10/13
 * \* Time: 12:18
 * \* Description:
 * \
 */
public class Activity {
    public static void main(String[] args) {
        int[] s = new int[] {1,3,0,5,3,5,6,8,8,2,12}; // 记录活动的开始时间
        int[] f = new int[] {4,5,6,7,8,9,10,11,12,13,14}; // 记录活动的结束时间
        int[] activitIndex = getActivitIndex(s, f);
        for (int i = 0; i < activitIndex.length; i++) {
            if(activitIndex[i] != 0)
            System.out.print(activitIndex[i] + " ");
        }
    }
    /**
     * 作用是 根据活动的结束时间，将活动的开始时间进行升序排序
     * @param f 活动的结束时间数组
     * @param s 活动的开始时间数组
     * @return
     * @author
     * @creed: Talk is cheap,show me the code
     * @date  2021年10月13日12:21:34
     */
    static void sortAction(int[] s,int[] f) {
        int i = 0 ,j = 0;
        int temp = 0;
        for (i = 0; i < f.length - 1 ; i++) {
            for(j = 0 ; j < f.length - 1 - i; j++) {
                if(f[j] > f[j + 1]) {
                    temp = s[j];
                    s[j] = s[j+1];
                    s[j+1] = temp;
                }
            }
        }
    }
    /**
     * 
     * @param s 活动的开始时间
     * @param f 活动的结束时间
     * @return 返回当天所有不冲突的活动
     * @author 
     * @creed: Talk is cheap,show me the code
     * @date  2021年10月13日12:24:35
     */
    static int[] getActivitIndex(int[] s, int[] f) {
        int[] index = new int[s.length];
        sortAction(s,f); // 将结束时间从小到大排序
        index[0] = 1; //第一个活动直接添加进去
        int endIndex = f[0]; // 记录第一个结束时间
        for (int i = 1; i < s.length; i++) {
                if(endIndex < s[i]) { // 如果前一个活动的结束时间小于下一个活动的开始时间
                    index[i] = i + 1; //那么此次活动就可以安排 加入到存放活动的数组中
                    endIndex = f[i]; // 将活动的结束时间置为本次加入活动的结束时间
                }
        }
        return index;
    }
}
